The present invention relates generally to static information storage and retrieval systems, and more particularly to associative memories, which are also referred to as content or tag memories.
Many real world applications today require searching information at high speed. In particular, as network-systems proliferate in which data packets are transferred based on the contents of address information contained there in, it is increasingly desirable to perform very high speed comparisons to deliver such data packets (xe2x80x9croutingxe2x80x9d and xe2x80x9cswitchingxe2x80x9d are the terms particularly used in the network field). This has motivated the network industry to turn to hardware solutions, including a class of circuits known as xe2x80x9ccontent addressable memoriesxe2x80x9d (CAM). The following discussion will generally use this example of packet routing and switching in networks, although many other applications also exist where high speed searching is desirable, and where the present invention may be useful.
The data packet routing and switching in networks generally employs a matching function, wherein a header field in the data packet is compared to a number of table entries. There are basically two types of information search which are of interest in this role, exact match search and partial match search.
For these two types of information searching two types of CAMs are available. Binary CAM can only be used for exact match search applications. Ternary CAM, on the other hand, can be configured and used for exact match and partial match search applications.
To some extent, CAM can be compared to more widely known random access memories (RAM). CAM cells must be both readable and writable, just like RAM cells. However, CAM operates in the converse way that RAM operates. In a RAM, the input is an address and the output is the data stored at that address. In a CAM, the input is a data sample and the output is a flag to indicate a match, as well as an address of matching data.
For example, a typical unit today is a 128 bit by 1024 (or 1K) CAM, which can be used to compare a 128 bit data sample against a xe2x80x9cdatabasexe2x80x9d of 1024 potential matches. The time period required for this is inherently short and is generally consistent despite the database size, ignoring extrinsic factors. It is this ability which CAMs provide to quickly search wide data words against large address spaces (databases) which makes them highly useful.
FIGS. 1a and 1b (background art) summarize examples of logic operation in binary and ternary CAM, respectively. In FIG. 1a, a binary CAM unit has the content of 1010 stored at address 0; the content of 1010 also stored at address 1; the content of 1100 stored at address 2; and the content of 1000 stored at address 3. If the data 1010 is input to this binary CAM, a flag indicates a match and an output of 0 is generated, indicating the first match address. If the data 1100 is input to this CAM, the flag again indicates a match and an output of 2 is generated, indicating the only match address this time. Finally, if the data 1001 is input, the flag does not indicate a match (any output should be ignored). In this example there will never be a output of 1, since we are presuming a prioritization which provides the lowest matching address.
In FIG. 1b, a ternary CAM unit has the content of 1010 with the mask 0000 stored at address 0; the content of 1010 with the mask 0001 stored at address 1; the content of 1100 with the mask 0000 stored at address 2; and the content of 1000 with the mask 0001 stored at address 3. If the data 1010 is input to this CAM, a flag indicates a match and an output of 0 is generated, indicating the first match address (again prioritized). If the data 1100 is input to this CAM, the flag again indicates a match and an output of 2 is generated, indicating the (only) match address. However, if the data 1001 is input to this ternary CAM, the flag indicates a match and an output of 3 is generated. This occurs because the mask here has filtered the last bit of the contentxe2x80x94with this content and mask data of either 1000 or 1001 this same result would be produced. Continuing, if the data 1101 is input to this ternary CAM, the flag here will not indicate a match.
In the above ternary CAM example there could potentially be a valid address output of 1. This would occur if the data 1011 were input. Also, in this ternary CAM example longest prefix type masks have been used. Such longest prefix masking is particularly useful in modern network routing and switching schemes, where the leading bits, or prefixes, of addresses are often all that is important in routing and switching.
FIG. 2 (background art) is a block diagram which stylistically depicts how a typical CAM unit 10 contains three logic blocks 12: a CAM array block 14, a match detection block 16, and a priority encoder block 18. A data input 20 and a result output 22 complete this simple representation.
The CAM array block 14 contains CAM cells and comparison logics, discussed presently, which receive a signal for comparison with a signal at the data input 20. The match detection block 16 contains logics to generate a match signal for each CAM entry. The priority encoder block 18 takes in the match signals (from the match detection block 16) and outputs the address of the highest priority matched entry, as a signal at the result output 22.
FIG. 3 (background art) is a block diagram which stylistically depicts how a typical binary CAM unit 30 includes three major logic blocks 32 (analogous to the logic blocks 12 of FIG. 2), and which particularly depicts the details of a CAM array block 34 and a match detection block 36. A priority encoder block 38 is also shown here, but not depicted in detail since it may be conventional (or even omitted). Finally, an input bus 40 (analogous to the simplified data input 20 of FIG. 2) and a result output 42 are also provided.
The binary CAM array block 34 contains many binary CAM cells 44. Each such binary CAM cell 44 typically consists of a comparator logic cell 46 and a content location 48, typically equivalent to a SRAM bit. All of the content locations 48 have entry data bits stored in them before the binary CAM unit 30 is used. The data to be searched (xe2x80x9ccomparedxe2x80x9d or xe2x80x9cmatchedxe2x80x9d) may then be provided on the input bus 40 (here extending from B0 to Bn). The unit data searched in a CAM is often referred to as a xe2x80x9cword,xe2x80x9d although this comparand data may be much longer than an 8-bit word, e.g., 32 bits or 128 bits are typical in current commercially available CAMs.
The comparator logic cell 46 basically compares the data on the input bus 40 with the data pre-stored in the content location 48, and then outputs a bit signal 52. FIG. 3a (background art) depicts a simplified gate logic equivalent of the comparator logic cell 46. The bit signal 52 is a 1 if the data are the same or a 0 if they are different (in principal, the logical inverse of an exclusive OR logic). In actual practice, say, at an integrated circuit die level other gate logic may be used or semiconductors may be employed in manners which blur distinction between individual logical units and thus may not form distinct xe2x80x9cgates.xe2x80x9d Accordingly, this is a conceptual representation, which skilled in the art will appreciate may be implemented in many different manners.
Returning to FIG. 3, all of the respective bit signals 52 output from the comparator logic cells 46, in a respective entry (row), go to the match detection block 36. The match detection block 36 includes a series of AND gates 54, one per respective entry (row) in the CAM. All of the bit signals 52 for a respective entry (row) are directed to one such AND gate 54, and if all of the respective bit signals 52 are true (all 1""s) the AND gate 54 generates a respective match signal 56. Again, this also is a conceptual representation of what may be employed in actuality.
These match signals 56, from the match detection block 36, then collectively go to the priority encoder block 38, where the result output 42 is generated. The priority encoder block 38 may be considered optional, theoretically, although one is almost always present, either integral to the CAM unit itself or in some form of external circuitry. The priority encoder block 38 addresses the situation when more than one AND gate 54 generates a match signal 56, i.e. when more than one entry is flagged as indicating a match. As noted previously, the purpose of a CAM includes providing an address of matching data. Thus, the signal at the result output 42 contains both a flag indicating whether a match occurred, as well as the address of one such match, if any matches occurred. Just one such address for matching data is included in the signal generated at the result output 42, based upon prioritization using a pre-set rule. For example, if multiple matches occur, the lowest match address may be used, the highest match address may be used, a randomly chosen match address may be used, etc. The prioritization rule is a matter of design choice.
Some liberties have been taken above to emphasize the salient aspects of CAM operation. In FIG. 3 the circuitry used for writing entries, i.e., the content locations 48 of the binary CAM unit 30, has been omitted. Also, most CAM today employs gate circuitry to control how the data is provided on the input bus 40. This has likewise been omitted. The match detection block 36 has also been described as using AND circuitry, but those skilled in the electronic arts will readily appreciate that other gate logic may be used instead. Furthermore, the priority encoder block 38 has been described only in general concept. This is because such other details are not germane to the present topic of binary verse ternary CAM, or generally to the present invention.
FIG. 4 (background art) is a block diagram which stylistically depicts how a typical ternary CAM unit 70 includes three major logic blocks 72 (analogous to the logic blocks 12 of FIG. 2), and which particularly depicts the details of a CAM array block 74 and a match detection block 76. A priority encoder block 78 is also shown here, but not depicted in detail since, as described above for binary CAMs, it may be conventional (or even omitted). Finally, an input bus 80 and a result output 82 are also provided.
The ternary CAM array block 74 contains many ternary CAM cells 84. Each such ternary CAM cell 84 typically consists of a comparator logic cell 86, as well as a content location 88 and a mask location 90, typically equivalent to two SRAM bits.
All of the content locations 88 have entry data stored in them before the ternary CAM unit 70 is used. Similarly, all of the mask locations 90 must have mask data stored in them. The data to be searched (compared) may then be provided on the input bus 80 (here extending from B0 to Bn).
The comparator logic cell 86 basically compares the data on the an input bus 80 with the data pre-stored in the content location 88 and the mask location 90 and then outputs a bit signal 92. FIG. 4a (background art) depicts a simplified gate logic equivalent of the comparator logic cell 86. Here also, in actual practice other gate logic or semiconductor-die implementations not even forming distinct gates may alternately be used.
Returning to FIG. 4, when not masked by a 1 in the mask location 90, the comparator logic cell 86 basically compares the data on the input bus 80 with the data pre-stored in the content location 88, just like the binary CAM array block 34 does (FIG. 3), and the comparator logic cell 86 outputs a bit signal 92 which is a 1 if the data are the same or a 0 if they are different. In contrast, when masked, the comparator logic cell 86 will always output the bit signal 92 as a 1. All of the respective bit signals 92 output from the comparator logic cells 86, in a respective entry (row), go to the match detection block 76.
The match detection block 76 includes a series of AND gates 94, one per respective entry (row) in the CAM. All of the bit signals 92 for a respective entry (row) are directed to one such AND gate 94, and if all of the respective bit signals 92 are true (all 1""s) the AND gate 94 generates a respective match signal 96.
It should be noted that the operations of the match detection block 76 and the priority encoder block 78 are essentially the same as for their equivalents in the binary CAM unit 30 of FIG. 3. What are depicted here are conceptual representations of what may be employed in actuality.
As described above with respect particularly to FIG. 3, in present binary CAM units each cell contains only one bit of information, the content location 48. This bit of information can be implemented using essentially any memory technology existing today, such as SRAM, DRAM, ROM, flash memory, etc. In contrast, as described above with respect particularly to FIG. 4, the cells in each ternary CAM unit contain two bits of information, both the content location 88 and the mask location 90. These two bits of information in ternary CAM cells can also be implemented using essentially any conventional memory technology.
Today binary and ternary CAM are discrete component types, typically implemented as integrated circuits, although discrete component implementations are still occasionally encountered. Most, if not all, CAM manufacturers presently supply only ternary CAM products, despite their lower xe2x80x9cdensity.xe2x80x9d This is because ternary CAM can also be used, interchangeably as binary CAM (e.g., by setting the mask locations 90 all to 0""s). The drawback to this, however, is that when ternary CAM is used as binary CAM all of the mask locations must be set to an off state, and hence half of the storage locations on a die are effectively wasted.
The use of ternary CAM as binary CAM is obviously not an efficient use of resources. A more desirable situation is to employ a CAM which is configurable, as either binary or ternary CAM, but which is efficient and fully utilizes all memory cells be in either mode. Unfortunately, until the advent of the present invention this more desirable solution has not been accomplished. The following discussion of some key prior art serves to illustrate this.
U.S. Pat. No. 6,108,227 by Vokel teaches a CAM in which the CAM cells are switchable between binary and ternary modes of operation by the use of a variable impedance path. This CAM can be particularly used interchangeably in both binary and ternary CAM modes, due to the improvement of a variable impedance path controlling the mode change. But this advancement in the art does not efficiently use all memory cells in either mode, it follows conventional practice and merely sets the mask locations to an off state when the ternary CAM is used in binary mode.
U.S. Pat. No. 6,044,005 by Gibson et al. also teaches CAM in which the CAM cells are switchable between binary and ternary modes of operation, but here particular gating and a reduced match line power dissipation facilitating the construction of large-capacity CAM arrays are provided. This therefore also follows conventional practice in the art, and does not efficiently use all of the available memory cells when the ternary CAM is used in binary mode.
Examples of other CAM related references which show the history and the general present state of the art include: U.S. Pat. No. 6,081,440 by Washburn et al. which teaches a ternary CAM having a massive parallel shift capability; U.S. Pat. No. 6,101,116 by Lien et al. which teaches a six-transistor CAM cell that prevents write operation disruption of non-written row contents; U.S. Pat. No. 6,061,262 by Schultz et al. which teaches a large-capacity CAM in which random access memory (RAM) core cells are used to store the CAM data; U.S. Pat. No. 5,940,852 by Rangasayee et al. which teaches a programmable logic device in which dual-mode memory is operable as a CAM or a RAM; U.S. Pat. No. 5,949,696 by Threewitt which teaches a three-state CAM cell with a comparison element for speed network address filtering; U.S. Pat. No. 5,517,441 by Dietz et al. which teaches a CAM in which faster comparisons are achieved by staggering the availability of information for comparison; U.S. Pat. No. 5,072,422 by Rachels which teaches a CAM having a plurality of word cells with logic enabling independent parallel operation of each word cell; U.S. Pat. No. 5,010,516 by Oates which teaches a CAM implemented with a plurality of integrated circuits; and U.S. Pat. No. 4,996,666 by Duluk Jr. which teaches an exemplary early CAM implementation.
Accordingly, what is needed is a design for an efficient and configurable binary-ternary CAM (BT-CAM), where all of the cells in can be fully utilized regardless of the configuration of the CAM.
Accordingly, it is an object of the present invention to provide a CAM which is configurable to operate in either binary mode or ternary mode, yet which is efficiently able to utilize all memory cells in either mode.
Briefly, a first preferred embodiment of the present invention is a content addressable memory (CAM) cell. A first storage location is provided into which a content bit can be stored, and a second storage location is provided into which either a content bit or a mask bit can be stored. A comparator logic cell is connected to each of a mode terminal, two input lines, and the first and second storage locations. When operation of the CAM cell in a binary mode is requested via the mode terminal, the comparator logic cell generates a bit signal based on comparison in two-bit binary manner of two data bits, respectively received on the input lines, and the content bits in each of the storage locations. Alternately, when operation of the CAM cell in a ternary mode is requested via the mode terminal, the comparator logic cell generates the bit signal based on comparison in one-bit ternary manner of one data bit, received on one of the input lines, with the content bit in the first storage location and using the mask bit in the second storage location.
Briefly, a second preferred embodiment of the present invention is a content addressable memory (CAM). An input bus is provided to receive a data signal including a plurality of data bits into an array block having a plurality of CAM cells. The CAM cells each include a first storage location into which a content bit can be stored and a second storage location into which either a content bit or a mask bit can be stored. Also included is a comparator logic cell which is connected to the input bus and the storage locations. The comparator logic cell is able to generate a bit signal based on comparison in two-bit binary manner of two of the data bits with the content bits respectively in each of the storage locations, when operation is desired in a binary mode. Alternately, the comparator logic cell are able to generate the bit signal based on comparison in one-bit ternary manner of one data bit with the content bit in the first storage location and the mask bit in the second storage location, when operation is desired in a ternary mode. A match detection block receives the bit signals from the array block and generates there from a plurality of match signals. A priority encoder block receives the plurality of match signals and generates there from a result signal at a result output.
Briefly, a third preferred embodiment of the present invention is a method for operating a content addressable memory (CAM) configurably in either of binary or ternary operation modes. A mode signal is received indicating which of the binary or the ternary operation modes is desired. When the mode signal indicates the binary operation mode is desired, a first data bit and a second data bit are received from a data signal and respectively compared to a first-part content bit previously stored in said first storage location and to a second-part content bit previously stored in said second storage location, thereby performing a two-bit binary comparison. A bit signal based is then generated based on this two-bit binary comparison. Alternately, when the mode signal indicates the ternary operation mode is desired, only the first data bit is received from the data signal and compared to a content bit previously stored in the first storage location. This is done based on a mask bit previously stored in the second storage location, thereby instead performing a one-bit ternary comparison. The bit signal is then generated based on this one-bit ternary comparison.
An advantage of the present invention is that it provides a general purpose CAM that may be used in either binary or ternary modes, thus eliminating the potential need for distinct parts that can operate in each mode or resorting to the use of a ternary CAM in an equivalent-binary manner.
Another advantage of the invention is that it provides a CAM which utilizes memory cells in a maximally efficient manner in both binary and ternary modes, thus providing a CAM with highest possible effective cell density in either mode.
And another advantage of the invention is that it provides a CAM which may be implement in as little as a single integrated circuit, which may be pin configurable to operate in either of binary or ternary modes, and which need not waste any die space or energy on inoperable cells when the CAM is used in binary mode.
These and other objects and advantages of the present invention will become clear to those skilled in the art in view of the description of the best presently known mode of carrying out the invention and the industrial applicability of the preferred embodiment as described herein and as illustrated in the several figures of the drawings.